package com.zjsru.oneDay;

/**
 * 找到小镇的法官,n为人数
 * <p>
 * 输入：n = 3, trust = [[1,3],[2,3],[3,1]]
 * 输出：-1
 * <p>
 * 输入：n = 2, trust = [[1,2]]
 * 输出：2
 * <p>
 * 输入：n = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
 * 输出：3
 */
public class findJudge {
    /**
     * 两个数组
     * @param n
     * @param trust
     * @return int
     */
    public int findJudge(int n, int[][] trust) {
        int[] in = new int[n + 1];
        int[] out = new int[n + 1];
        for (int[] t : trust) {
            int a = t[0],b = t[1];
            in[b]++;
            out[a]++;
        }
        for (int i = 1; i <= n; i++) {
            if (in[i] == n - 1 && out[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 一个数组
     * @param n
     * @param trust
     * @return int
     */
    public int findJudge2(int n, int[][] trust) {
        int[] degrees = new int[n + 1];
        for (int[] t : trust) {
            int x = t[0];
            int y = t[1];
            // 出度+1
            degrees[x]--;
            // 入度+1
            degrees[y]++;
        }
        // 找到入度-出度为 n-1 的人
        for (int i = 1; i <= n; i++) {
            if (degrees[i] == n - 1) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        findJudge findJudge = new findJudge();
       // int[][] trust = new int[][]{{1, 3}, {2, 3}, {3, 1}};
        int[][] trust1 = new int[][]{{1, 2}};
        int result = findJudge.findJudge(2, trust1);
        System.out.println(result);
    }

}
